home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / zoo21src.zoo / lzd.c < prev    next >
C/C++ Source or Header  |  1991-07-24  |  31KB  |  852 lines
  1. #ifndef LINT
  2. static char sccsid[]="@(#) lzd.c 2.6 88/01/30 20:39:18";
  3. #endif /* LINT */
  4.  
  5. /*********************************************************************/
  6. /* This file contains two versions of the lzd() decompression routine.
  7. The default is to use a fast version coded by Ray Gardner.  If the
  8. symbol SLOW_LZD is defined, the older slower one is used.  I have tested
  9. Ray's code and it seems to be portable and reliable.  But if you
  10. suspect any problems you can define SLOW_LZD for your system in
  11. options.h and cause the older code to be used.  --R.D. */
  12. /*********************************************************************/
  13.  
  14. #include "options.h"
  15. #include "zoo.h"
  16. #include "zooio.h"
  17. #include "various.h"
  18. #include "zoofns.h"           /* function definitions */
  19. #include "zoomem.h"
  20. #include "debug.h"
  21. #include "assert.h"
  22. #include "lzconst.h"
  23.  
  24. #ifndef SLOW_LZD
  25.  
  26. /* Extensive modifications for speed by Ray Gardner
  27. ** Public domain by Raymond D. Gardner  9/26/88
  28. **
  29. ** I apologize for the comments being so dense in places as to impair
  30. ** readability, but some of the stuff isn't very obvious and needs
  31. ** some explaining.  I am also sorry for the messy control structure
  32. ** (quite a few labels and goto's) and very long lzd() function, but
  33. ** I don't know how to do this any other way without loss of speed.
  34. **
  35. ** Ray Gardner
  36. ** 6374 S. Monaco Ct.
  37. ** Englewood, CO 80111
  38. */
  39.  
  40. #ifdef ANSI_HDRS
  41. # include <string.h>        /* to get memcpy */
  42. #else
  43.   VOIDPTR memcpy();
  44. #endif
  45.  
  46. #define  STACKSIZE   4000  /* allows for about 8Mb string in worst case? */
  47. /* stack grows backwards in this version, using pointers, not counters */
  48. static char *stack;
  49. static char *stack_pointer;
  50. static char *stack_lim;
  51.  
  52. void init_dtab PARMS((void));
  53. unsigned rd_dcode PARMS((void));
  54. /* void wr_dchar (char); */        /* now a macro */
  55. void ad_dcode PARMS((void));
  56.  
  57. #ifdef FILTER
  58. /* to send data back to zoofilt */
  59. extern unsigned int filt_lzd_word;
  60. #endif /* FILTER */
  61.  
  62. #ifndef __GNUC__
  63. void xwr_dchar PARMS ((char));
  64. #else
  65. void xwr_dchar PARMS ((int));
  66. #endif /* __GNUC__ */
  67. static int firstchar PARMS ((int));
  68. static void cbfill PARMS ((void));
  69.  
  70. /* wr_dchar() is a macro for speed */
  71. #define wr_dchar(c) {                             \
  72.                            if (outbufp<outbuflim) \
  73.                               *outbufp++=(c);     \
  74.                            else                   \
  75.                               xwr_dchar(c);       \
  76.                     }
  77.  
  78. extern char *out_buf_adr;        /* output buffer */
  79. extern char *in_buf_adr;         /* input buffer */
  80.                       /* use pointers (not counters) for buffer (for speed) */
  81. static char *outbufp;            /* output buffer pointer */
  82. static char *outbuflim;          /* output buffer limit */
  83. static char *outbufguard;        /* output buffer "guard" */
  84.  
  85. char memflag = 0;                /* memory allocated? flag */
  86. int *head;                       /* lzw prefix codes */
  87. char *tail;                      /* lzw suffix codes */
  88. static unsigned cur_code;
  89. static unsigned old_code;
  90. static unsigned in_code;
  91.  
  92. static unsigned free_code;
  93. static int nbits;
  94. static unsigned max_code;
  95.  
  96. /* We use a buffer of codes to avoid a function call to unpack each
  97. ** one as needed.  We allocate an extra slot past the end of the buffer
  98. ** and put a CLEAR code in it, to serve as a sentinel.  This way we can
  99. ** fold the test for code buffer runout into the test for a clear code
  100. ** and avoid having an extra test on each code processed.  Also, we don't
  101. ** always use the code buffer.  We can only use it when the input buffer
  102. ** is at a byte boundary, and when we know that the codesize won't change
  103. ** before we fill the code buffer, and when we know we won't run out of
  104. ** bytes in the input buffer before filling the code buffer.  So we start
  105. ** with the code buffer pointer pointing to the sentinel, and we always
  106. ** have it pointing at the sentinel when we can't (for one reason or
  107. ** another) be getting our codes from the code buffer.  We check for this
  108. ** condition whenever we get a CLEAR code, and if so, we get the code
  109. ** via the good old rd_dcode() routine.
  110. **
  111. ** One other problem with the code buffer approach is that we might get
  112. ** a CLEAR code in the middle of the buffer.  This means that the next
  113. ** code is only 9 bits, but we have probably already unpacked a number of
  114. ** larger codes from the input into the buffer before we discover this.
  115. ** So we remember where (in the input buffer) the code buffer was filled
  116. ** from, and when a CLEAR code is encountered in the buffer (not the
  117. ** sentinel at the end) we back up the bit_offset pointer in the input
  118. ** buffer, and reset things to start unpacking the 9-bit codes from there.
  119. */
  120.  
  121. #define CODEBUF_SIZE 64      /* must be multiple of 8, experiment for best */
  122. static unsigned codebuf[CODEBUF_SIZE+1];     /* code buffer */
  123. static unsigned *codebufp;       /* code buffer pointer */
  124. static unsigned *codebuflim;     /* code buffer limit */
  125.       /* bit offset within the input buffer of where the code buffer began */
  126. static unsigned codebufoffset;
  127.  
  128. static unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  129.                         0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
  130. static unsigned bit_offset;   /* note this only allows max 8K input buffer!!*/
  131.  
  132. #ifdef UNBUF_IO
  133. #define        BLOCKFILE        int
  134. #define        BLOCKREAD        read
  135. #define        BLOCKWRITE        blockwrite
  136. int read PARMS ((int, VOIDPTR, unsigned));
  137. int write PARMS ((int, VOIDPTR, unsigned));
  138. int blockwrite PARMS ((int, VOIDPTR, unsigned));
  139. #else
  140. #define        BLOCKFILE        ZOOFILE
  141. #define        BLOCKREAD        zooread
  142. #define        BLOCKWRITE        zoowrite
  143. #endif /* UNBUF_IO */
  144.  
  145. static BLOCKFILE in_f, out_f;
  146.  
  147. /* rd_dcode() reads a code from the input (compressed) file and returns
  148. its value. */
  149. unsigned rd_dcode()
  150. {
  151.    register char *ptra, *ptrb;    /* miscellaneous pointers */
  152.    unsigned word;                     /* first 16 bits in buffer */
  153.    unsigned byte_offset;
  154.    char nextch;                           /* next 8 bits in buffer */
  155.    unsigned ofs_inbyte;               /* offset within byte */
  156.  
  157.    ofs_inbyte = bit_offset % 8;
  158.    byte_offset = bit_offset / 8;
  159.    bit_offset = bit_offset + nbits;
  160.  
  161.    assert(nbits >= 9 && nbits <= 13);
  162.  
  163.    if (byte_offset >= INBUFSIZ - 5) {
  164.       int space_left;
  165.  
  166.       assert(byte_offset >= INBUFSIZ - 5);
  167.       debug((printf ("lzd: byte_offset near end of buffer\n")))
  168.  
  169.       bit_offset = ofs_inbyte + nbits;
  170.       space_left = INBUFSIZ - byte_offset;
  171.       ptrb = byte_offset + in_buf_adr;          /* point to char */
  172.       ptra = in_buf_adr;
  173.       /* we now move the remaining characters down buffer beginning */
  174.       debug((printf ("rd_dcode: space_left = %d\n", space_left)))
  175.       while (space_left > 0) {
  176.          *ptra++ = *ptrb++;
  177.          space_left--;
  178.       }
  179.       assert(ptra - in_buf_adr == ptrb - (in_buf_adr + byte_offset));
  180.       assert(space_left == 0);
  181.       if (BLOCKREAD (in_f, ptra, byte_offset) == -1)
  182.          prterror ('f', "I/O error in lzd:rd_dcode.\n");
  183.       byte_offset = 0;
  184.    }
  185.    ptra = byte_offset + in_buf_adr;
  186.  /* NOTE:  "word = *((int *) ptra)" would not be independent of byte order. */
  187.    word = (unsigned char) *ptra; ptra++;
  188.    word = word | ( ((unsigned char) *ptra) << 8 ); ptra++;
  189.  
  190.    nextch = *ptra;
  191.    if (ofs_inbyte != 0) {
  192.       /* shift nextch right by ofs_inbyte bits */
  193.       /* and shift those bits right into word; */
  194.       word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
  195.    }
  196.    return (word & masks[nbits]); 
  197. } /* rd_dcode() */
  198.  
  199. void init_dtab()
  200. {
  201.    nbits = 9;
  202.    max_code = 512;
  203.    free_code = FIRST_FREE;
  204. }
  205.  
  206. /* By making wr_dchar() a macro and calling this routine only on buffer
  207. ** full condition, we save a lot of function call overhead.
  208. ** We also use pointers instead of counters for efficiency (in the macro).
  209. */
  210. void xwr_dchar (ch)
  211. char ch;
  212. {
  213.    if (outbufp >= outbuflim) {      /* if buffer full */
  214.       if (BLOCKWRITE (out_f, out_buf_adr, (outbufp - out_buf_adr))
  215.                                                 != out